package sorting2;

public class QuickSortMediana3 {

	private void calculoDaMediana3(int[] array, int esquerda, int direita){
		int centro = (esquerda + direita)/2;

		if (array[centro] < array[esquerda]){
			array = swap(array, centro, esquerda);
		}
		if (array[direita] < array[esquerda]){
			array = swap(array, direita, esquerda);
		}
		if (array[direita] < array[centro]){
			array = swap(array, direita, centro);
		}

		swap(array, centro, direita-1);
	}

	public int[] quickSortMediana3(int[] array, int comecoDoArray, int fimDoArray){

		if (comecoDoArray >= fimDoArray){
			return array;
		}

		calculoDaMediana3(array, comecoDoArray, fimDoArray);


		int esquerda = comecoDoArray + 1;
		int direita = fimDoArray - 2;
		int p = array[fimDoArray - 1];

		if (esquerda > direita ){
			return array;
		}

		while ( true ){
			while ( array[esquerda] < p) {
				esquerda ++;

			}
			while ( array[direita] > p) {
				direita --;
			}
			if (esquerda < direita ){
				array = swap(array, esquerda, direita);
			} else {
				break;
			}

		}

		array = swap(array, fimDoArray - 1, esquerda);

		quickSortMediana3(array, comecoDoArray, esquerda - 1);
		quickSortMediana3(array, esquerda + 1, fimDoArray);

		return array;
	} 

	private int[] swap(int[] array, int menor, int maior){
		int temporario = array[maior];
		array[maior] = array[menor];
		array[menor] = temporario;

		return array;

	}

}